
#pragma once

#include <atomic>
#include <chrono>  // NOLINT
#include <cstdint>
#include <list>
#include <mutex>  // NOLINT
#include <vector>
#include <unordered_map>
#include <vector>
#include <iostream>


namespace bustub {

/** Cycle detection is performed every CYCLE_DETECTION_INTERVAL milliseconds. */
extern std::chrono::milliseconds cycle_detection_interval;

/** True if logging should be enabled, false otherwise. */
extern std::atomic<bool> enable_logging;

/** If ENABLE_LOGGING is true, the log should be flushed to disk every LOG_TIMEOUT. */
extern std::chrono::duration<int64_t> log_timeout;

static constexpr int INVALID_PAGE_ID = -1;                                           // invalid page id
static constexpr int INVALID_TXN_ID = -1;                                            // invalid transaction id
static constexpr int INVALID_LSN = -1;                                               // invalid log sequence number
static constexpr int HEADER_PAGE_ID = 0;                                             // the header page id
static constexpr int BUSTUB_PAGE_SIZE = 4096;                                        // size of a data page in byte
static constexpr int BUFFER_POOL_SIZE = 10;                                          // size of buffer pool
static constexpr int LOG_BUFFER_SIZE = ((BUFFER_POOL_SIZE + 1) * BUSTUB_PAGE_SIZE);  // size of a log buffer in byte
static constexpr int BUCKET_SIZE = 50;                                               // size of extendible hash bucket
static constexpr int LRUK_REPLACER_K = 10;  // lookback window for lru-k replacer

using frame_id_t = int32_t;    // frame id type
using page_id_t = int32_t;     // page id type
using txn_id_t = int32_t;      // transaction id type
using lsn_t = int32_t;         // log sequence number type
using slot_offset_t = size_t;  // slot offset type
using oid_t = uint16_t;

static constexpr int VARCHAR_DEFAULT_LENGTH = 128;  // default length for varchar when constructing the column

}  // namespace bustub


namespace bustub {

/**
 * Replacer is an abstract class that tracks page usage.
 */
class Replacer {
 public:
  Replacer() = default;
  virtual ~Replacer() = default;

  /**
   * Remove the victim frame as defined by the replacement policy.
   * @param[out] frame_id id of frame that was removed, nullptr if no victim was found
   * @return true if a victim frame was found, false otherwise
   */
  virtual auto Victim(frame_id_t *frame_id) -> bool = 0;

  /**
   * Pins a frame, indicating that it should not be victimized until it is unpinned.
   * @param frame_id the id of the frame to pin
   */
  virtual void Pin(frame_id_t frame_id) = 0;

  /**
   * Unpins a frame, indicating that it can now be victimized.
   * @param frame_id the id of the frame to unpin
   */
  virtual void Unpin(frame_id_t frame_id) = 0;

  /** @return the number of elements in the replacer that can be victimized */
  virtual auto Size() -> size_t = 0;
};

}  // namespace bustub


namespace bustub {

/**
 * LRUReplacer implements the Least Recently Used replacement policy.
 */
class LRUReplacer : public Replacer {
 public:
  /**
   * Create a new LRUReplacer.
   * @param num_pages the maximum number of pages the LRUReplacer will be required to store
   */
  explicit LRUReplacer(size_t num_pages);

  /**
   * Destroys the LRUReplacer.
   */
  ~LRUReplacer() override;

  auto Victim(frame_id_t *frame_id) -> bool override;

  void Pin(frame_id_t frame_id) override;

  void Unpin(frame_id_t frame_id) override;

  auto Size() -> size_t override;

 private:
  // TODO(student): implement me!
    std::mutex mut_all_pages;
    std::mutex mut_page_idxs;
    std::mutex mut_size;
    std::list<int> all_pages;
    uint32_t num_pages;
    uint32_t size;
    std::unordered_map<int,int> page_idxs;//1 pin   0 unpin



};

}  // namespace bustub

namespace bustub {

LRUReplacer::LRUReplacer(size_t num_pages) {
    this->num_pages = num_pages;
    this->size=0;
}

LRUReplacer::~LRUReplacer() = default;

auto LRUReplacer::Victim(frame_id_t *frame_id) -> bool { 
    //TODO  size 的调整，页面被删除之后，需要将unpin里面的也删除
    int flag=0;
    this->mut_all_pages.lock();
    std::list<int>::reverse_iterator iter;
    for(auto node=this->all_pages.rbegin();node!=all_pages.rend();node++){
        this->mut_page_idxs.lock();
        if(page_idxs.count(*node)>0||page_idxs[*node]==0){//元素存在，但是锁的标记为0,如果元素不存在
            this->mut_page_idxs.unlock();                 //表明frame中已经不存在这个页面了
            iter = node;
            flag=1;
            break;
        }
        this->mut_page_idxs.unlock();
    }
    if(flag){
        *frame_id = *iter;
        all_pages.erase((++iter).base());
        page_idxs.erase(*(++iter).base());
        this->mut_size.lock();
        this->size--;
        this->mut_size.unlock();
        
    }
    this->mut_all_pages.unlock();
    if(flag)
        return true;
    return false; 
}

void LRUReplacer::Pin(frame_id_t frame_id) {
    this->mut_page_idxs.lock();
    if(this->page_idxs.count(frame_id)>0){//如果存在这个页面则执行，如果锁一个不存的页面，直接跳过
        if(this->page_idxs[frame_id]==0){//没锁
            this->page_idxs[frame_id]=1; //锁上，并且将size减一，可删除页面减小
            this->mut_size.lock();
            this->size--;
            this->mut_size.unlock();
        }//如果这个页面之前锁上了，就不执行
    }
    this->mut_page_idxs.unlock();
}

void LRUReplacer::Unpin(frame_id_t frame_id) {
    this->mut_all_pages.lock();
    this->mut_page_idxs.lock();
    this->mut_size.lock();

    if(this->page_idxs.count(frame_id)<=0){
        this->size++;
        this->all_pages.push_front(frame_id);
    }
    this->page_idxs[frame_id]=0;
    
    this->mut_size.unlock();
    this->mut_page_idxs.unlock();
    this->mut_all_pages.unlock();
}

auto LRUReplacer::Size() -> size_t { 
    this->mut_size.lock();
    size_t size = this->size;
    this->mut_size.unlock();
    return size;
}

}  // namespace bustub

int main(){
    using namespace bustub;
    using namespace std;
    LRUReplacer lru_replacer(7);

    // Scenario: unpin six elements, i.e. add them to the replacer.
    lru_replacer.Unpin(1);
    lru_replacer.Unpin(2);
    lru_replacer.Unpin(3);
    lru_replacer.Unpin(4);
    lru_replacer.Unpin(5);
    lru_replacer.Unpin(6);
    lru_replacer.Unpin(1);
    int size=0;
    if((size=lru_replacer.Size())==6){
        cout<<"size is right"<<endl;
    }else{
        cout<<"ERROR size "<<size<<endl;
    }

    int value;
    lru_replacer.Victim(&value);
    if(value==1){
        cout<<"value is right"<<endl;
    }else{
        cout<<"ERROR value "<<value<<endl;
    }
    lru_replacer.Victim(&value);
    if(value==2){
        cout<<"value is right"<<endl;
    }else{
        cout<<"ERROR value "<<value<<endl;
    }
    lru_replacer.Victim(&value);
    if(value==3){//有问题
        cout<<"value is right"<<endl;
    }else{
        cout<<"ERROR value "<<value<<endl;
    }




}


#ifdef DEBUG

TEST(LRUReplacerTest, DISABLED_SampleTest) {
  LRUReplacer lru_replacer(7);

  // Scenario: unpin six elements, i.e. add them to the replacer.
  lru_replacer.Unpin(1);
  lru_replacer.Unpin(2);
  lru_replacer.Unpin(3);
  lru_replacer.Unpin(4);
  lru_replacer.Unpin(5);
  lru_replacer.Unpin(6);
  lru_replacer.Unpin(1);
  EXPECT_EQ(6, lru_replacer.Size());

  // Scenario: get three victims from the lru.
  int value;
  lru_replacer.Victim(&value);
  EXPECT_EQ(1, value);
  lru_replacer.Victim(&value);
  EXPECT_EQ(2, value);
  lru_replacer.Victim(&value);
  EXPECT_EQ(3, value);

  // Scenario: pin elements in the replacer.
  // Note that 3 has already been victimized, so pinning 3 should have no effect.
  lru_replacer.Pin(3);
  lru_replacer.Pin(4);
  EXPECT_EQ(2, lru_replacer.Size());

  // Scenario: unpin 4. We expect that the reference bit of 4 will be set to 1.
  lru_replacer.Unpin(4);

  // Scenario: continue looking for victims. We expect these victims.
  lru_replacer.Victim(&value);
  EXPECT_EQ(5, value);
  lru_replacer.Victim(&value);
  EXPECT_EQ(6, value);
  lru_replacer.Victim(&value);
  EXPECT_EQ(4, value);
}

#endif